279. 完全平方数
279. 完全平方数
分析
多个完全平方数的和为 n，假设组成和的最大的完全平方数 x，应该有
我们按照动态规划五部曲来解题
定义 dp 数组：dp[j] 为放满容量为 j 的背包时候组成 j 的完全平方数的最小个数。
状态转移方程：dp[j] = Math.min(dp[j],1+dp[j-nums[i]]);，因为我们求的是背包被塞满的情况下的最小物品个数。因此使用这个状态转移方程需要同时满足两个条件，
- 使用物品 i 的时候，
dp[j-nums[i]]得有值（存在能塞满容量为j-nums[i]的背包的完全平方数的组合） - 不使用物品 i 的时候，
dp[j]得有值（存在能塞满容量为 j 的背包的完全平方数的组合）
因此我们需要判断，
- 如果
dp[j-nums[i]]有值- 如果
dp[j]有值，使用状态转移方程：dp[j] = Math.min(dp[j],1+dp[j-nums[i]]); - 如果
dp[j]没值，直接dp[j] = 1+dp[j-nums[i]];
- 如果
- 如果
dp[j-nums[i]]没有值，直接放弃更新dp[j]
为什么别的放满背包的题目不需要考虑不能存在组合的情况，请看 322. 零钱兑换#分析
初始化的情况。
因为 dp[j] 存在两种情况，
- 不存在多个物品可能凑满背包的组合
- 存在多个物品可能凑满背包的组合，而且组合的最小个数为
dp[j]
因此为了区分这两种情况，我们把 dp 数组的所有元素初始化为 -1，同时 dp[0]=0; 因为塞满容量为 0 的背包的物品数量为 0.
然后是遍历顺序，因为求的是最小组合数，所以可以不在乎内外层 for 哪个在外面哪个在里面，于是我们选择更好理解的，外层 for 循环遍历物品，内层 for 循环遍历容量，而且因为是完全背包，所以从 nums[i] 遍历到容量最大值。如果是 01 背包，就得从容量最大值遍历到 nums[i] 了。
为什么可以不在乎内外层 for 哪个在外面哪个在里面？请看 377. 组合总和 Ⅳ#什么时候可以不在乎内外层 for 循环哪个在外面哪个在里面
小优化
其实在使用状态转移公式之前，也可以不判断 dp[j-nums[i]]、dp[j] 是否有值，因为 n 一定可以拆成多个 1 的和，而 1 是完全平方数，所以 dp[j-nums[i]] 至少都是有一个值，就是 j-nums[i]，不会是 -1。把 dp 数组输出就可以确认这一点了。
例如 n=12，输出的 dp 数组为
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 3, 4, 5, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
[0, 1, 2, 3, 1, 2, 3, 4, 2, 1, 2, 3, 3]
确实没有 -1。
因此可以简化。
解题
class Solution {
public int numSquares(int n) {
// 这道题跟零钱兑换没有区别，只是将物品换成了 从 1 到n的n个数，用这些数的平方凑出 n
int[] dp = new int[n+1];
Arrays.fill(dp,-1);
dp[0]= 0;
// dp[]
// num 的长度为n; 同时 num[i] = (i+1)*(i+1)
for(int i=0;i<n;i++){
int ele = (i+1)*(i+1);
for(int j=ele;j<=n;j++){
if(dp[j-ele]>-1){
if(dp[j]>-1){
dp[j] = Math.min(dp[j],dp[j-ele]+1);
}else{
dp[j] = dp[j-ele]+1;
}
}
}
}
return dp[n];
}
}
简化
public int numSquares(int n) {
int[] nums = new int[n];
for(int i=1;i<=n;i++){
nums[i-1]=i*i;
}
int[] dp = new int[n+1];
for(int i=0;i<n+1;i++){
dp[i]=Integer.MAX_VALUE;
}
dp[0]=0;
for(int i=0;i<nums.length;i++){
for(int j=nums[i];j<n+1;j++){
dp[j] = Math.min(dp[j], 1+ dp[j-nums[i]]);
}
}
return dp[n];
}